package 二叉树的最近公共祖先;

/**
 * @author AirMan
 * @version 1.0
 * @description 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * 例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
 * @date 2025/4/6 20:45
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归
        // 递归的参数：TreeNode root, TreeNode p, TreeNode q
        // 递归的返回值：TreeNode
        // 递归的终止条件：root == null,但是当root == q || root == p时，需要返回当前的root
        // 单层递归的逻辑：采用左右中的后序遍历，进行自底向上遍历。遍历过程中如果遇到该节点是p或者q那么就返回p或者q
        // 如果遇到一边返回的是null，一边返回的是非null，那么返回非null节点
        // 如果左右都不为null，那么返回当前的根结点

        // 遍历整棵树
        if (root == null || root == q || root == p)
            return root;
        // left
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        // right
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // root
        if (left != null && right != null)
            return root;
        else if (left != null || right == null)
            return left;
        else
            return right; // right可能为null，也可能不为null
    }
}
